﻿/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution24
{

    //迭代
    public ListNode SwapPairs2(ListNode head)
    {

        if (head == null || head.next == null)
        {
            return head;
        }

        ListNode dummyhead = new ListNode();
        dummyhead.next = head;
        ListNode pre = dummyhead;
        ListNode cur = dummyhead;
        ListNode next = dummyhead;
        while (pre.next != null && pre.next.next != null)
        {

            cur = pre.next;
            next = cur.next;




            cur.next = next.next;
            next.next = cur;
            pre.next = next;


            pre = cur;


        }


        return dummyhead.next;





    }
    //递归
    public ListNode SwapPairs(ListNode head)
    {

        if (head == null || head.next == null)
        {
            return head;
        }

        ListNode newHead= head.next;
       

        head.next = SwapPairs(newHead.next);

        newHead.next = head;
        return newHead;


    } 

    }

class Program24
{
    static void Main24(string[] args)
    {
        ListNode head = new ListNode(1);
        ListNode next = new ListNode(2);
        head.next = next;

        Solution24 solution = new Solution24();
       solution.SwapPairs(head);
      

    }
}